题目描述 给定两个字符串A和B,现在要将A经过若干操作变为B,可进行的操作有: 删除–将字符串A中的某个字符删除。 插入–在字符串A的某个位置插入某个字符。 替换–将字符串A中的某个字符替换为另一个字符。 现在请你求出,将A变为B至少需要进行多少次操作。
输入格式 1 2 3 4 5 第一行包含整数n,表示字符串A的长度。 第二行包含一个长度为n的字符串A。 第三行包含整数m,表示字符串B的长度。 第四行包含一个长度为m的字符串B。 字符串中均只包含大写字母。
输出格式
数据范围
输入样例: 1 2 3 4 10 AGTCTGACGC 11 AGTAAGTAGGC
输出样例:
解题思路 二维dp问题
状态表示:
dp[i][j]
表示第一个字符串的前i个字母编辑到第二个字符串的前j个字母的最小编辑距离
状态计算:
枚举字符串a前i个字母到字符串b前j个字母的最后一步的操作(增/删/改)
添加一个字母:
要先做到a的前i个字母与b的前j - 1个字母匹配
, a[1~i]添加一个字母才能与b[1~j]匹配
dp[i][j] = dp[i - 1][j] + 1
删除一个字母:
要先做到a的前i - 1个字母与b的前j个字母匹配
,a[1~i]添加一个字母才能与b[1~j]匹配
dp[i][j] = dp[i][j - 1] + 1
修改一个字母
要先做到a[1~i-1]与b[1~j-1]匹配
a[i]与b[j]相同: dp[i][j] = dp[i - 1][j - 1]
a[i]与b[j]不同: dp[i][j] = dp[i - 1][j - 1] + 1
状态转移方程:
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (a[i] != b[j]))
代码 C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <iostream> #include <algorithm> using namespace std ;const int N = 1010 ;int n, m;char a[N], b[N];int f[N][N];int main () { cin >> n; for (int i = 1 ; i <= n; i ++) { cin >> a[i]; f[i][0 ] = i; } cin >> m; for (int i = 1 ; i <= m; i ++) { cin >> b[i]; f[0 ][i] = i; } for (int i = 1 ; i <= n; i ++) for (int j = 1 ; j <= m; j++) { f[i][j] = min(f[i - 1 ][j] + 1 , f[i][j - 1 ] + 1 ); f[i][j] = min(f[i][j], f[i - 1 ][j - 1 ] + int (a[i] != b[j])); } cout << f[n][m] << endl ; return 0 ; }
Python: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def main () : n = int(input()) a = ' ' + input() m = int(input()) b = ' ' + input() f = [[0 ] * (m + 1 ) for _ in range(n + 1 )] for i in range(1 , n + 1 ): f[i][0 ] = i for i in range(1 , m + 1 ): f[0 ][i] = i for i in range(1 , n + 1 ): for j in range(1 , m + 1 ): f[i][j] = min(f[i - 1 ][j] + 1 , f[i][j - 1 ] + 1 , f[i - 1 ][j - 1 ] + (a[i] != b[j])) print(f[n][m]) main()
给定n个长度不超过10的字符串以及m次询问,每次询问给出一个字符串和一个操作次数上限。
对于每次询问,请你求出给定的n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
输入格式
第一行包含两个整数n和m。
接下来n行,每行包含一个字符串,表示给定的字符串。
再接下来m行,每行包含一个字符串和一个整数,表示一次询问。
字符串中只包含小写字母,且长度均不超过10。
输出格式
输出共m行,每行输出一个整数作为结果,表示一次询问中满足条件的字符串个数。
数据范围
输入样例: 1 2 3 4 5 6 3 2 abc acd bcd ab 1 acbd 2
输出样例:
解题思路 最短编辑距离的应用, 求n次最短编辑距离
代码 C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <iostream> #include <string.h> #include <algorithm> using namespace std ;const int N = 1010 , M = 20 ;int n, m;char s[N][M];int f[M][M];bool can_solve (char a[], char b[], int t) { int la = strlen (a + 1 ), lb = strlen (b + 1 ); f[0 ][0 ] = 0 ; for (int i = 1 ; i <= la; i++) f[i][0 ] = i; for (int i = 1 ; i <= lb; i++) f[0 ][i] = i; for (int i = 1 ; i <= la; i++) for (int j = 1 ; j <= lb; j++) { f[i][j] = min(f[i - 1 ][j] + 1 , f[i][j - 1 ] + 1 ); f[i][j] = min(f[i][j], f[i - 1 ][j - 1 ] + int (a[i] != b[j])); } return f[la][lb] <= t; } int main () { cin >> n >> m; for (int i = 0 ; i < n; i++) cin >> s[i] + 1 ; while (m --) { int res = 0 ; int t; char q[M]; cin >> q + 1 >> t; for (int j = 0 ; j < n; j++) res += can_solve(s[j], q, t); cout << res << endl ; } return 0 ; }
Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 def can_solve (a, b, t) : """ 求字符串a是否能在t的次数内编辑到b 为了方便计算, a和b在前面随便加个字符占位 """ a = ' ' + a b = ' ' + b la, lb = len(a), len(b) dp = [[0 ] * lb for _ in range(la)] for i in range(la): dp[i][0 ] = i for i in range(lb): dp[0 ][i] = i for i in range(1 , la): for j in range(1 , lb): dp[i][j] = min(dp[i - 1 ][j] + 1 , dp[i][j - 1 ] + 1 , dp[i - 1 ][j - 1 ] + (a[i] != b[j])) return dp[la - 1 ][lb - 1 ] <= t def main () : n, m = [int(x) for x in input().split()] s = [] for _ in range(n): s.append(input()) for _ in range(m): q, t = input().split() t = int(t) res = 0 for i in range(n): res += can_solve(s[i], q, t) print(res) main()